using System;
using System.Collections.Generic;
using System.Collections;

namespace needle.Services.astra.Collections
{
	/// <summary>
	/// List of items, which uses inner item indexes to access actual items, which are stored in items store (different list(s)).
	/// This list can represent full set, subset or any combination of items of actual items store.
	/// This list does not specify, where the items are stored actually.
	/// </summary>
	/// <typeparam name="T">Item type.</typeparam>
	public abstract class IndexBasedList<T> : IItemsChangeList<T>
	{
		/// <summary>
		/// Used to set <see cref="IndexBasedList{}._listItemsChangeLock"/> value.
		/// </summary>
		private struct ListItemsChangeLockSetter : IDisposable
		{
			/// <summary>
			/// Increments <see cref="IndexBasedList{}._listItemsChangeLock"/>.
			/// </summary>
			/// <param name="list">List.</param>
			public ListItemsChangeLockSetter(IndexBasedList<T> list)
			{
				_list = list;
				_list._listItemsChangeLock++;
			}

			#region IDisposable Members

			/// <summary>
			/// Decrements <see cref="IndexBasedList{}._listItemsChangeLock"/>.
			/// </summary>
			public void Dispose()
			{
				_list._listItemsChangeLock--;
			}

			#endregion

			/// <summary>
			/// List.
			/// </summary>
			private IndexBasedList<T> _list;
		}


		/// <summary>
		/// Constructor.
		/// </summary>
		public IndexBasedList()
		{
			_innerIndexesInnerList = new List<int>();
			_innerIndexes = new ItemsChangeList<int>(_innerIndexesInnerList);
			_innerIndexes.ItemsChange += InnerIndexes_ItemsChange;
		}

		/// <summary>
		/// List of inner indexes which are translated to actual items.
		/// </summary>
		/// <remarks>
		/// This list is used for <see cref="IList{}"/> implementation.
		/// </remarks>
		public IList<int> InnerIndexes
		{
			get { return _innerIndexes; }
		}
		/// <summary>
		/// If true, <see cref="InnerIndexes"/> is ignored and not modified.
		/// </summary>
		public bool IsUnited
		{
			get { return _isUnited; }
			set
			{
				if (_isUnited == value)
					return;
				_isUnited = value;
				OnItemsReset();
			}
		}
		/// <summary>
		/// Items <see cref="Count"/> which is used when <see cref="IsUnited"/> is true.
		/// </summary>
		public abstract int UnitedCount
		{
			get;
		}
		/// <summary>
		/// If true, when filtering, all removed items are removed from actual items store with <see cref="RemoveAt"/>, otherwise they are removed only from <see cref="InnerIndexes"/>.
		/// </summary>
		/// <value>Default: false.</value>
		public bool RemoveItemsWhileFiltering
		{
			get { return _removeItemsWhileFiltering; }
			set { _removeItemsWhileFiltering = value; }
		}

		/// <summary>
		/// Gets inner index from <paramref name="index"/>.
		/// </summary>
		/// <param name="index">Index.</param>
		/// <returns>
		/// If <see cref="IsUnited"/> is false, item (index) at <paramref name="index"/> from <see cref="InnerIndexes"/> is returned, otherwise <see cref="GetUnitedInnerIndex"/> for <paramref name="index"/> is returned.
		/// </returns>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <paramref name="index"/> is &lt; 0 or &gt;= <see cref="Count"/>.
		/// </exception>
		public int GetInnerIndex(int index)
		{
			if (index < 0)
				throw new ArgumentOutOfRangeException("index", index, "Must be in the range <0, Count).");
			if (this.IsUnited)
				return GetUnitedInnerIndex(index);
			else
				return this.InnerIndexes[index];
		}
		/// <summary>
		/// Gets outer index from <paramref name="innerIndex"/>.
		/// </summary>
		/// <param name="innerIndex">Inner index.</param>
		/// <returns>
		/// If <see cref="IsUnited"/> is false, index of <paramref name="innerIndex"/> from <see cref="InnerIndexes"/> is returned, otherwise <see cref="GetUnitedIndex"/> for <paramref name="innerIndex"/> is returned.
		/// If <paramref name="innerIndex"/> is invalid or not found, -1 is returned.
		/// </returns>
		public int GetIndex(int innerIndex)
		{
			if (this.IsUnited)
			{
				int index = GetUnitedIndex(innerIndex);
				if (index < 0 || index >= this.UnitedCount)
					return -1;
				else
					return index;
			}
			else
				return this.InnerIndexes.IndexOf(innerIndex);
		}
		/// <summary>
		/// Copies specified items to <paramref name="array"/>.
		/// </summary>
		/// <param name="index">Starting index of this list.</param>
		/// <param name="array">Target array.</param>
		/// <param name="arrayIndex">Starting index of target array from which items will be assigned.</param>
		/// <param name="count">Number of items to copy from this list.</param>
		/// <exception cref="ArgumentNullException"><paramref name="array"/> is null.</exception>
		/// <exception cref="ArgumentException"><paramref name="array"/> does not have enough space or is multidimensional.</exception>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <paramref name="index"/> is &lt; 0 or &gt;= <see cref="Count"/>.
		/// </exception>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <paramref name="count"/> is &lt;= 0 or is bigger then available items from <paramref name="index"/> to the end of the list.
		/// </exception>
		/// <exception cref="ArgumentOutOfRangeException"><paramref name="arrayIndex"/> is &lt; 0.</exception>
		public void CopyTo(int index, T[] array, int arrayIndex, int count)
		{
			if (index < 0)
				throw new ArgumentOutOfRangeException("index", index, "Must be >= 0.");
			if (index >= this.Count)
				throw new ArgumentOutOfRangeException("index", index, "Must be < Count.");
			if (count <= 0)
				throw new ArgumentOutOfRangeException("count", count, "Must be > 0.");
			if (count >= this.Count - index)
				throw new ArgumentOutOfRangeException("count", count, "So many items are not available.");
			if (array == null)
				throw new ArgumentNullException("array");
			if (array.Rank != 1)
				throw new ArgumentException("Must be one dimensional.", "array");
			if (arrayIndex < 0)
				throw new ArgumentOutOfRangeException("arrayIndex", arrayIndex, "Must be >= 0.");
			if (array.Length - arrayIndex < count)
				throw new ArgumentException("Does not have enough space.", "array");
			for (int i = 0; i < count; i++)
			{
				array[arrayIndex + i] = this[index + i];
			}
		}
		/// <summary>
		/// Sorts range of list items without affecting actual items store.
		/// </summary>
		/// <remarks>If <see cref="IsUnited"/> is true before sorting, <see cref="UniteInnerIndexes"/> is called first and <see cref="IsUnited"/> is set to false.</remarks>
		/// <param name="index">Starting index of a range of items to be sorted.</param>
		/// <param name="count">Number of items to be sorted from <paramref name="index"/>.</param>
		/// <param name="comparison">
		/// Items comparison used for sorting.
		/// If null, <see cref="Comparer{T}.Default"/> is used.
		/// </param>
		public void Sort(int index, int count, Comparison<T> comparison)
		{
			using (SuppressListItemsChange())
			{
				UniteInnerIndexesIfUnited();
				_innerIndexesInnerList.Sort(index, count, GetInnerIndexComparer(comparison));
			}
			OnItemsReset();
		}
		/// <summary>
		/// Sorts all list items without affecting actual items store.
		/// </summary>
		/// <remarks>If <see cref="IsUnited"/> is true before sorting, <see cref="UniteInnerIndexes"/> is called first and <see cref="IsUnited"/> is set to false.</remarks>
		/// <param name="comparison">
		/// Items comparison used for sorting.
		/// If null, <see cref="Comparer{T}.Default"/> is used.
		/// </param>
		public void Sort(Comparison<T> comparison)
		{
			using (SuppressListItemsChange())
			{
				UniteInnerIndexesIfUnited();
				_innerIndexesInnerList.Sort(GetInnerIndexComparison(comparison));
			}
			OnItemsReset();
		}
		/// <summary>
		/// Filters range of list items.
		/// </summary>
		/// <remarks>If <see cref="IsUnited"/> is true before filtering, <see cref="UniteInnerIndexes"/> is called first and <see cref="IsUnited"/> is set to false.</remarks>
		/// <param name="index">Starting index of a range of items to be filtered.</param>
		/// <param name="count">Number of items to be filtered from <paramref name="index"/>.</param>
		/// <param name="filter">
		/// Filter used for filtering.
		/// Items it returns false for are removed (see <see cref="RemoveItemsWhileFiltering"/>).
		/// </param>
		/// <exception cref="ArgumentNullException"><paramref name="filter"/> is null.</exception>
		public void Filter(int index, int count, Predicate<T> filter)
		{
			if (filter == null)
				throw new ArgumentNullException("filter");
			bool changed = false;
			using (SuppressListItemsChange())
			{
				changed = UniteInnerIndexesIfUnited();
				T item;
				for (int i = index + count - 1; i >= index; i--)
				{
					item = this[i];
					if (!filter(item))
					{
						changed = true;
						if (this.RemoveItemsWhileFiltering)
							RemoveAt(i);
						else
							_innerIndexesInnerList.RemoveAt(i);
					}
				}
			}
			if (changed)
				OnItemsReset();
		}
		/// <summary>
		/// Filters all list items.
		/// </summary>
		/// <remarks>If <see cref="IsUnited"/> is true before filtering, <see cref="UniteInnerIndexes"/> is called first and <see cref="IsUnited"/> is set to false.</remarks>
		/// <param name="filter">
		/// Filter used for filtering.
		/// Items it returns false for are removed (see <see cref="RemoveItemsWhileFiltering"/>).
		/// </param>
		/// <exception cref="ArgumentNullException"><paramref name="filter"/> is null.</exception>
		public void Filter(Predicate<T> filter)
		{
			Filter(0, this.Count, filter);
		}
		/// <summary>
		/// Clears <see cref="InnerIndexes"/> and fills it with <see cref="UnitedCount"/> of items (inner indexes) pointing to all inner items.
		/// </summary>
		public void UniteInnerIndexes()
		{
			using (SuppressListItemsChange())
			{
				_innerIndexesInnerList.Clear();
				int count = this.UnitedCount;
				_innerIndexesInnerList.Capacity = count;
				for (int i = 0; i < count; i++)
					_innerIndexesInnerList.Add(GetUnitedInnerIndex(i));
			}
			if (!this.IsUnited)
				OnItemsReset();
		}

		/// <summary>
		/// Gets inner index from <paramref name="index"/> for <see cref="IsUnited"/> is true case.
		/// </summary>
		/// <remarks>This implementation returns unchanged <paramref name="index"/>.</remarks>
		/// <param name="index">
		/// United outer index in the range &lt;0, <see cref="UnitedCount"/>&gt;. Its validity is not checked.
		/// </param>
		/// <returns>Inner index.</returns>
		protected abstract int GetUnitedInnerIndex(int index);
		/// <summary>
		/// Gets outer index from <paramref name="innerIndex"/> for <see cref="IsUnited"/> is true case.
		/// </summary>
		/// <param name="innerIndex">Inner index.</param>
		/// <returns>
		/// Outer index if <paramref name="innerIndex"/> which does not need to be valid (checked in <see cref="GetIndex"/>).
		/// </returns>
		protected abstract int GetUnitedIndex(int innerIndex);
		/// <summary>
		/// Gets last united outer index (as if <see cref="IsUnited"/> was true) for items substore in which <paramref name="item"/> will be or is stored.
		/// Example:
		/// If the substore is composed of two lists of items and the item is in first list, returned value is united index of last item in the first list.
		/// </summary>
		/// <param name="innerIndex">Item.</param>
		/// <returns>United index.</returns>
		protected abstract int GetLastUnitedIndexInSubstore(T item);
		/// <summary>
		/// Gets actual item at <paramref name="innerIndex"/> position.
		/// </summary>
		/// <param name="innerIndex">Inner index.</param>
		/// <returns>Item</returns>
		protected abstract T GetItem(int innerIndex);
		/// <summary>
		/// Sets actual <paramref name="item"/> at <paramref name="innerIndex"/> position.
		/// </summary>
		/// <param name="innerIndex">Inner index.</param>
		/// <param name="item">Item.</param>
		protected abstract void SetItem(int innerIndex, T item);
		/// <summary>
		/// Inserts <paramref name="item"/> at <paramref name="index"/> position.
		/// </summary>
		/// <param name="index">
		/// Outter <see cref="IList{}"/> index.
		/// When it is <see cref="Count"/>, item is added to the end of the list.
		/// </param>
		/// <param name="item">Item.</param>
		/// <returns>
		/// Inner index of inserted item.
		/// If <see cref="IsUnited"/> is false, <paramref name="item"/> can be added to the end of inner items store and <paramref name="index"/> can be ignored.
		/// </returns>
		protected abstract int InsertItem(int index, T item);
		/// <summary>
		/// Removes item at <paramref name="innerIndex"/> position.
		/// </summary>
		/// <param name="innerIndex">Inner index.</param>
		protected abstract void RemoveItem(int innerIndex);
		/// <summary>
		/// Removes all items from the list.
		/// </summary>
		protected abstract void ClearItems();
		/// <summary>
		/// Gets <see cref="IComparer{int}"/> from <paramref name="comparison"/>.
		/// </summary>
		/// <remarks>Calls <see cref="GetInnerIndexComparison"/>.</remarks>
		/// <param name="comparison">Comparison of list items.</param>
		/// <returns>Comparer of inner indexes.</returns>
		protected IComparer<int> GetInnerIndexComparer(Comparison<T> comparison)
		{
			if (comparison == null)
				return null;
			Comparison<int> innerIndexComparison = GetInnerIndexComparison(comparison);
			return ComparisonHelper<int>.GetComparer(innerIndexComparison);
		}
		/// <summary>
		/// Gets <see cref="Comparison{int}"/> from <paramref name="comparison"/>.
		/// </summary>
		/// <remarks>Uses <see cref="GetItem"/>.</remarks>
		/// <param name="comparison">Comparison of list items.</param>
		/// <returns>Comparison of inner indexes.</returns>
		protected Comparison<int> GetInnerIndexComparison(Comparison<T> comparison)
		{
			if (comparison == null)
				return null;
			return delegate(int xInnerIndex, int yInnerIndex)
				{
					T xItem = GetItem(xInnerIndex);
					T yItem = GetItem(yInnerIndex);
					return comparison(xItem, yItem);
				};
		}
		/// <summary>
		/// Calls <see cref="UniteInnerIndexes"/> if <see cref="IsUnited"/> is true and sets it to false, otherwise does nothing.
		/// </summary>
		/// <returns>Whether list was united.</returns>
		protected bool UniteInnerIndexesIfUnited()
		{
			if (!this.IsUnited)
				return false;
			using (SuppressListItemsChange())
			{
				UniteInnerIndexes();
			}
			this.IsUnited = false;
			return true;
		}
		/// <summary>
		/// Removes all occurrences of <paramref name="innerIndex"/> from <see cref="InnerIndexes"/> without change notifications.
		/// </summary>
		/// <param name="innerIndex">Inner index to be removed.</param>
		/// <param name="lastRemovedIndex">Index of last removed inner index. -1 if none is removed.</param>
		/// <returns>Number of removed inner indexes.</returns>
		protected int RemoveInnerIndex(int innerIndex, out int lastRemovedIndex)
		{
			int localInnerIndex;
			int removedIndexesCount = 0;
			lastRemovedIndex = -1;
			for (int i = _innerIndexesInnerList.Count - 1; i >= 0; i--)
			{
				localInnerIndex = _innerIndexesInnerList[i];
				if (localInnerIndex != innerIndex)
					continue;
				_innerIndexesInnerList.RemoveAt(i);
				removedIndexesCount++;
				if (lastRemovedIndex < 0)
					lastRemovedIndex = i;
			}
			return removedIndexesCount;
		}

		/// <summary>
		/// Changes inner indexes in <see cref="InnerIndexes"/> without notifications about the changes.
		/// The change is given by <paramref name="fromUnitedIndex"/>, <paramref name="toUnitedIndex"/> or <paramref name="increment"/> parameters.
		/// </summary>
		/// <param name="fromUnitedIndex">
		/// Begining united index of the rage of inner indexes to be changed.
		/// If null, 0 is used.
		/// </param>
		/// <param name="toUnitedIndex">
		/// Ending united index of the rage of inner indexes to be changed.
		/// If null, <see cref="UnitedCount"/> - 1 is used.
		/// </param>
		/// <param name="newFromInnerIndex">
		/// If not null, value is set to all inner indexes given by <paramref name="fromUnitedIndex"/> and <paramref name="increment"/> is ignored in this case.
		/// </param>
		/// <param name="newToInnerIndex">
		/// If not null, value is set to all inner indexes given by <paramref name="toUnitedIndex"/> and <paramref name="increment"/> is ignored in this case.
		/// </param>
		/// <param name="increment">Value to be added to united index got from old inner index and the result is converted back to new inner index and the old value is replaced with the new one.</param>
		/// <exception cref="ArgumentException">
		/// <paramref name="fromUnitedIndex"/> is &gt; <paramref name="toUnitedIndex"/>.
		/// </exception>
		/// <exception cref="ArgumentOutOfRangeException">
		/// <paramref name="fromUnitedIndex"/> is &gt;= <see cref="UnitedCount"/>.
		/// </exception>
		private void ChangeInnerIndexes(int? fromUnitedIndex, int? toUnitedIndex,
			int? newFromInnerIndex, int? newToInnerIndex, int increment)
		{
			if (fromUnitedIndex == null)
				fromUnitedIndex = 0;
			if (toUnitedIndex == null)
				toUnitedIndex = this.UnitedCount - 1;
			if (fromUnitedIndex > toUnitedIndex)
				throw new ArgumentException("fromUnitedIndex must be <= toUnitedIndex.");
			if (fromUnitedIndex >= this.UnitedCount)
				throw new ArgumentOutOfRangeException("fromUnitedIndex", fromUnitedIndex, "Must be < UnitedCount.");
			int fromInnerIndex = GetUnitedInnerIndex(fromUnitedIndex.Value);
			int toInnerIndex = GetUnitedInnerIndex(toUnitedIndex.Value);
			int innerIndex, unitedIndex;
			for (int i = _innerIndexesInnerList.Count - 1; i >= 0; i--)
			{
				innerIndex = _innerIndexesInnerList[i];
				unitedIndex = GetUnitedIndex(innerIndex);
				if (unitedIndex < fromUnitedIndex || unitedIndex > toUnitedIndex)
					continue;
				if (newFromInnerIndex != null && innerIndex == fromInnerIndex)
				{
					_innerIndexesInnerList[i] = newFromInnerIndex.Value;
					continue;
				}
				if (newToInnerIndex != null && innerIndex == toInnerIndex)
				{
					_innerIndexesInnerList[i] = newToInnerIndex.Value;
					continue;
				}
				innerIndex = GetUnitedInnerIndex(unitedIndex + increment);
				_innerIndexesInnerList[i] = innerIndex;
			}
		}

		#region Events

		#region IItemsChangeList<T> Members

		/// <summary>
		/// Fired when one of <see cref="ListItemsChanges"/> occures.
		/// </summary>
		public event EventHandler<ListItemsChangeEventArgs<T>> ItemsChange;

		#endregion

		/// <summary>
		/// Whether <see cref="OnItemsChange"/> will fire event.
		/// If false, <see cref="IItemsChangeList{T}.ItemsChange"/> event from item store should be ignored and not translated.
		/// </summary>
		protected bool AllowListItemsChange
		{
			get { return _listItemsChangeLock == 0; }
		}

		/// <summary>
		/// Fires <see cref="ItemsChange"/> event when <see cref="AllowListItemsChange"/> is true.
		/// Derived class should always call this base method when it overrides it.
		/// </summary>
		/// <param name="e">Event arguments.</param>
		protected virtual void OnItemsChange(ListItemsChangeEventArgs<T> e)
		{
			if (this.AllowListItemsChange && this.ItemsChange != null)
				this.ItemsChange(this, e);
		}
		/// <summary>
		/// Called when new item is inserted into the list.
		/// </summary>
		/// <remarks>Calls <see cref="OnItemsChange"/>.</remarks>
		/// <param name="index">Index of item.</param>
		/// <param name="item">Item.</param>
		protected virtual void OnItemInserted(int index, T item)
		{
			OnItemsChange(new ListItemsChangeEventArgs<T>(ListItemsChanges.Add, item, index));
		}
		/// <summary>
		/// Called when item is removed from the list.
		/// </summary>
		/// <remarks>Calls <see cref="OnItemsChange"/>.</remarks>
		/// <param name="index">Index of item before it was removed.</param>
		/// <param name="item">Item (which does not need to be activated).</param>
		protected virtual void OnItemRemoved(int index, T item)
		{
			OnItemsChange(new ListItemsChangeEventArgs<T>(ListItemsChanges.Remove, item, index));
		}
		/// <summary>
		/// Called when item is replaced in the list.
		/// </summary>
		/// <remarks>Calls <see cref="OnItemsChange"/>.</remarks>
		/// <param name="index">Index of item.</param>
		/// <param name="newItem">New item.</param>
		/// <param name="oldItem">Old item.</param>
		protected virtual void OnItemReplaced(int index, T newItem, T oldItem)
		{
			OnItemsChange(new ListItemsChangeEventArgs<T>(ListItemsChanges.Replace, newItem, oldItem, index));
		}
		/// <summary>
		/// Called when item is moved in the list.
		/// </summary>
		/// <remarks>Calls <see cref="OnItemsChange"/>.</remarks>
		/// <param name="newIndex">New index of item.</param>
		/// <param name="oldIndex">Old index of item.</param>
		/// <param name="item">Item.</param>
		protected virtual void OnItemMoved(int newIndex, int oldIndex, T item)
		{
			OnItemsChange(new ListItemsChangeEventArgs<T>(ListItemsChanges.Move, item, newIndex, oldIndex));
		}
		/// <summary>
		/// Called when the list changed dramatically (filtering, sorting, clearing, initializing, ...).
		/// </summary>
		/// <remarks>Calls <see cref="OnItemsChange"/>.</remarks>
		protected virtual void OnItemsReset()
		{
			OnItemsChange(new ListItemsChangeEventArgs<T>(ListItemsChanges.Reset));
		}

		/// <summary>
		/// Supresses <see cref="ItemsChange"/> event (see <see cref="OnItemsChange"/>).
		/// </summary>
		protected IDisposable SuppressListItemsChange()
		{
			return new ListItemsChangeLockSetter(this);
		}
		/// <summary>
		/// Translates <see cref="IItemsChangeList{}.ItemsChange"/> event from inner items store (list) to local <see cref="OnItemsChange"/> call.
		/// </summary>
		/// <remarks>
		/// If <see cref="AllowListItemsChange"/> is false does nothing.
		/// </remarks>
		/// <param name="change">Type of change.</param>
		/// <param name="newItem">New item.</param>
		/// <param name="oldItem">Old item.</param>
		/// <param name="newUnitedIndex">New united outer index.</param>
		/// <param name="oldUnitedIndex">Old united outer index.</param>
		protected virtual void TranslateInnerItemsChange(ListItemsChanges change,
			T newItem, T oldItem, int newUnitedIndex, int oldUnitedIndex)
		{
			if (!this.AllowListItemsChange)
				return;
			int newInnerIndex = GetUnitedInnerIndex(newUnitedIndex);
			int oldInnerIndex = GetUnitedInnerIndex(oldUnitedIndex);
			int newIndex = -1;
			int oldIndex = -1;
			switch (change)
			{
				// in ununited list, new item will not be added to InnerIndexes
				case ListItemsChanges.Add:
					if (this.IsUnited)
					{
						OnItemInserted(GetIndex(newInnerIndex), newItem);
					}
					// no outer change, but we change inner indexes
					else
					{
						int lastUnitedIndexInSubstore = GetLastUnitedIndexInSubstore(newItem);
						if (newUnitedIndex < lastUnitedIndexInSubstore)
							ChangeInnerIndexes(newUnitedIndex + 1, lastUnitedIndexInSubstore, null, null, 1);
						return;
					}
					break;
				// in ununited list, inner index(es) of removed item will be removed from InnerIndexes, if found
				case ListItemsChanges.Remove:
					int removedIndexesCount = 1;
					if (this.IsUnited)
						oldIndex = GetIndex(oldInnerIndex);
					else
						removedIndexesCount = RemoveInnerIndex(oldInnerIndex, out oldIndex);
					if (removedIndexesCount > 1)
						OnItemsReset();
					else if (removedIndexesCount == 1)
					{
						// change inner indexes
						if (!this.IsUnited)
						{
							int lastUnitedIndexInSubstore = GetLastUnitedIndexInSubstore(oldItem);
							if (oldUnitedIndex < lastUnitedIndexInSubstore)
								ChangeInnerIndexes(oldUnitedIndex, lastUnitedIndexInSubstore, null, null, -1);
						}
						OnItemRemoved(oldIndex, oldItem);
					}
					else
						return;
					break;
				case ListItemsChanges.Replace:
					newIndex = GetIndex(newInnerIndex);
					if (newIndex < 0)
						return;
					int replacedIndexesCount = 1;
					if (!this.IsUnited)
					{
						int lastIndex = _innerIndexesInnerList.IndexOf(newIndex, newIndex + 1);
						// at least 2 same items are replaced
						if (lastIndex >= 0)
							replacedIndexesCount++;
					}
					if (replacedIndexesCount > 1)
						OnItemsReset();
					else
						OnItemReplaced(newIndex, newItem, oldItem);
					break;
				case ListItemsChanges.Move:
					if (oldUnitedIndex == newUnitedIndex)
						return;
					if (this.IsUnited)
					{
						newIndex = GetIndex(newInnerIndex);
						oldIndex = GetIndex(oldInnerIndex);
						OnItemMoved(newIndex, oldIndex, newItem);
					}
					// no outer change, but we change inner indexes
					else
					{
						if (oldUnitedIndex < newUnitedIndex)
							ChangeInnerIndexes(oldUnitedIndex, newUnitedIndex, oldInnerIndex, null, -1);
						else
							ChangeInnerIndexes(newUnitedIndex, oldUnitedIndex, null, newInnerIndex, 1);
						return;
					}
					break;
				// if inner items are resetted, we unite the list
				case ListItemsChanges.Reset:
					if (this.IsUnited)
						OnItemsReset();
					else
						this.IsUnited = true;
					break;
			}
		}

		/// <summary>
		/// Translates <see cref="IItemsChangeList{T}.ItemsChange"/> event from <see cref="InnerIndexes"/> to local <see cref="OnItemsChange"/> call.
		/// </summary>
		/// <remarks>
		/// If <see cref="AllowListItemsChange"/> is false or <see cref="IsUnited"/> is true, does nothing.
		/// </remarks>
		private void InnerIndexes_ItemsChange(object sender, ListItemsChangeEventArgs<int> e)
		{
			if (!this.AllowListItemsChange || this.IsUnited)
				return;
			switch (e.Change)
			{
				case ListItemsChanges.Add:
					OnItemInserted(e.NewIndex, GetItem(e.NewItem));
					break;
				case ListItemsChanges.Remove:
					OnItemRemoved(e.OldIndex, GetItem(e.OldItem));
					break;
				case ListItemsChanges.Replace:
					OnItemReplaced(e.NewIndex, GetItem(e.NewItem), GetItem(e.OldItem));
					break;
				case ListItemsChanges.Move:
					return;
				case ListItemsChanges.Reset:
					OnItemsReset();
					break;
			}
		}

		/// <summary>
		/// See <see cref="AllowListItemsChange"/>.
		/// </summary>
		private int _listItemsChangeLock;

		#endregion

		#region IList<T> Members

		/// <summary>
		/// See <see cref="IList{}.IndexOf"/>.
		/// </summary>
		/// <remarks>Uses <see cref="EqualityComparer{T}.Default"/>.</remarks>
		public int IndexOf(T item)
		{
			for (int i = this.Count - 1; i >= 0; i--)
			{
				if (EqualityComparer<T>.Default.Equals(this[i], item))
					return i;
			}
			return -1;
		}
		/// <summary>
		/// See <see cref="IList{}.Insert"/>.
		/// </summary>
		/// <remarks>Calls <see cref="InsertItem"/>.</remarks>
		public void Insert(int index, T item)
		{
			using (SuppressListItemsChange())
			{
				if (!this.IsUnited)
					this.InnerIndexes.Insert(index, int.MinValue);
				try
				{
					int innerIndex = InsertItem(index, item);
					if (!this.IsUnited)
						this.InnerIndexes[index] = innerIndex;
				}
				catch (Exception)
				{
					if (!this.IsUnited)
						this.InnerIndexes.RemoveAt(index);
					throw;
				}
			}
			OnItemInserted(index, item);
		}
		/// <summary>
		/// See <see cref="IList{}.RemoveAt"/>.
		/// </summary>
		/// <remarks>Calls <see cref="RemoveItem"/>.</remarks>
		public void RemoveAt(int index)
		{
			int innerIndex = GetInnerIndex(index);
			T item = GetItem(innerIndex);
			using (SuppressListItemsChange())
			{
				if (!this.IsUnited)
					this.InnerIndexes.RemoveAt(index);
				try
				{
					RemoveItem(innerIndex);
				}
				catch (Exception)
				{
					if (!this.IsUnited)
						this.InnerIndexes.Insert(index, innerIndex);
					throw;
				}
			}
			OnItemRemoved(index, item);
		}
		/// <summary>
		/// See <see cref="IList{}.Item[]"/>.
		/// </summary>
		/// <remarks>
		/// get: Calls <see cref="GetItem"/>.
		/// set: Calls <see cref="SetItem"/>.
		/// </remarks>
		public T this[int index]
		{
			get
			{
				return GetItem(GetInnerIndex(index));
			}
			set
			{
				int innerIndex = GetInnerIndex(index);
				T oldItem = GetItem(innerIndex);
				using (SuppressListItemsChange())
				{
					SetItem(innerIndex, value);
				}
				OnItemReplaced(index, value, oldItem);
			}
		}

		#endregion

		#region ICollection<T> Members

		/// <summary>
		/// See <see cref="ICollection{}.Add"/>.
		/// </summary>
		public void Add(T item)
		{
			Insert(GetLastUnitedIndexInSubstore(item) + 1, item);
		}
		/// <summary>
		/// See <see cref="ICollection{}.Clear"/>.
		/// </summary>
		/// <remarks>Calls <see cref="ClearItems"/>.</remarks>
		public void Clear()
		{
			using (SuppressListItemsChange())
			{
				ClearItems();
				if (!this.IsUnited)
					this.InnerIndexes.Clear();
			}
			OnItemsReset();
		}
		/// <summary>
		/// See <see cref="ICollection{}.Contains"/>.
		/// </summary>
		public bool Contains(T item)
		{
			return IndexOf(item) >= 0;
		}
		/// <summary>
		/// See <see cref="ICollection{}.CopyTo"/>.
		/// </summary>
		/// <remarks>Calls <see cref="CopyTo(int, T[], int, int)"/>.</remarks>
		public void CopyTo(T[] array, int arrayIndex)
		{
			CopyTo(0, array, arrayIndex, this.Count);
		}
		/// <summary>
		/// See <see cref="ICollection{}.Count"/>.
		/// </summary>
		/// <remarks>
		/// If <see cref="IsUnited"/> is true, calls <see cref="UnitedCount"/>, otherwise returns <see cref="InnerIndexes"/>`s items count.
		/// </remarks>
		public int Count
		{
			get
			{
				if (this.IsUnited)
					return UnitedCount;
				else
					return this.InnerIndexes.Count;
			}
		}
		/// <summary>
		/// See <see cref="ICollection{}.IsReadOnly"/>.
		/// </summary>
		public abstract bool IsReadOnly
		{
			get;
		}
		/// <summary>
		/// See <see cref="ICollection{}.Remove"/>.
		/// </summary>
		public bool Remove(T item)
		{
			int index = IndexOf(item);
			if (index < 0)
				return false;
			try
			{
				RemoveAt(index);
			}
			catch (Exception)
			{
				return false;
			}
			return true;
		}

		#endregion

		#region IEnumerable<T> Members

		/// <summary>
		/// See <see cref="IEnumerable{}.GetEnumerator"/>.
		/// </summary>
		public IEnumerator<T> GetEnumerator()
		{
			int count = this.Count;
			for (int i = 0; i < count; i++)
			{
				yield return this[i];
			}
		}

		#endregion

		#region IEnumerable Members

		/// <summary>
		/// See <see cref="IEnumerable.GetEnumerator"/>.
		/// </summary>
		IEnumerator IEnumerable.GetEnumerator()
		{
			return GetEnumerator();
		}

		#endregion

		/// <summary>
		/// See <see cref="InnerIndexes"/>.
		/// </summary>
		private ItemsChangeList<int> _innerIndexes;
		/// <summary>
		/// Inner list wrapped by <see cref="_innerIndexes"/>.
		/// </summary>
		private List<int> _innerIndexesInnerList;
		/// <summary>
		/// See <see cref="IsUnited"/>.
		/// </summary>
		private bool _isUnited = true;
		/// <summary>
		/// See <see cref="RemoveItemsWhileFiltering"/>.
		/// </summary>
		private bool _removeItemsWhileFiltering;
	}
}
